This invention relates to a method and system for thinning images in an image data processing system. More specifically, this invention relates to use of a processor for extracting centroid lines (medial axes) from binary images.
There are various imaging systems in which processing of image data is very helpful in order to allow better recognition of particular features. For example, a sonar system uses various data processing techniques to improve target identification and classification. An infrared imaging system may likewise use data processing techniques to improve target identification in connection with a weapons system. Image data processing for making certain features or objects more recognizable may also be used in conjunction with various medical imaging techniques. A tomographic medical imaging system might use data processing techniques to make a tumor more recognizable.
Imaging systems may use a thinning process in order to make certain features stand out. The image data would be Boolean, meaning that each pixel is either one or zero (i.e., black or white; or on or off). If the image is not initially Boolean, the image data is clipped or compared to a threshold in order to produce a Boolean image. The process of thinning involves whittling away at images in the image data from all four sides. By performing this process sufficiently, all pixels remaining in the one state either represent one-pixel dots, or connect in such a way as to represent a line or lines. Certain features such as potential targets within a zone of interest (i.e., the zone subjected to imaging) will be more easily recognizable, either by a person viewing the image or by pattern recognition computer arrangements.
An image of conventional size, such as 512 pixels by 512 lines, consists of more than a quarter million pixels. Such an image may be conveniently processed on a parallel computing machine structured for Boolean operations such as the Thinking Machines Corp Connection Machine. However, it is extremely time consuming to perform a thinning process on a machine structured and used primarily for floating point arithmetic. Certain applications, such as target identification in military imaging systems, must process large amounts of image data in real time. Ideally, one would use a parallel computing machine structured for Boolean operations for performing the thinning process and would use a machine (floating point processor) structured and used primarily for floating point arithmetic in order to perform the numerous floating point operations commonly required in conjunction with such target imaging systems. However, it often is too expensive to have a Boolean processor for Boolean operations and a separate floating point processor for the various math floating point operations. At the same time, a floating point processor is poorly structured to handle the numerous if statements commonly required for thinning processes. A floating point processor may simply be unable to handle the required if statements quickly enough to allow real time thinning of images.
U.S. Pat. No. 5,062,142 issued on Oct. 29, 1991 to John R Meckley, one of the co-inventors of the present application. That patent, which is assigned to the assignee of the present application and hereby incorporated by reference, discloses a process and system for producing medial axis representations by thinning image data. A target pixel is considered for possible change by latching values of pixels in its neighborhood to generate an address supplied to a look-up table. Although that invention is very useful, the specific techniques described therein are not well-suited for use in a floating point processor type of system.